// https://leetcode.cn/problems/24-game/

// 算法思路总结：
// 1. 使用深度优先搜索枚举所有可能的运算组合
// 2. 每次选择两个数字，进行六种运算（考虑交换律）
// 3. 递归处理剩余数字和运算结果，检查是否得到24
// 4. 使用EPS处理浮点数精度问题
// 5. 时间复杂度：O(1)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <cmath>

class Solution 
{
private:
    const double EPS = 1e-6;
    string solution;
    
    bool dfs(vector<double>& nums, vector<string>& exprs) 
    {
        int n = nums.size();
        if (n == 1) 
        {
            if (fabs(nums[0] - 24) < EPS) 
            {
                solution = exprs[0];
                return true;
            }
            return false;
        }
        
        for (int i = 0 ; i < n ; i++) 
        {
            for (int j = i + 1 ; j < n ; j++) 
            { 
                vector<double> nextNums;
                vector<string> nextExprs;
                
                for (int k = 0 ; k < n ; k++) 
                {
                    if (k != i && k != j) 
                    {
                        nextNums.push_back(nums[k]);
                        nextExprs.push_back(exprs[k]);
                    }
                }
                
                double a = nums[i], b = nums[j];
                string exprA = exprs[i], exprB = exprs[j];
                
                vector<pair<double, string>> operations = 
                {
                    {a + b, "(" + exprA + " + " + exprB + ")"},
                    {a - b, "(" + exprA + " - " + exprB + ")"},
                    {b - a, "(" + exprB + " - " + exprA + ")"},
                    {a * b, "(" + exprA + " * " + exprB + ")"}
                };
                
                if (fabs(b) > EPS) 
                {
                    operations.push_back({a / b, "(" + exprA + " / " + exprB + ")"});
                }
                if (fabs(a) > EPS) 
                {
                    operations.push_back({b / a, "(" + exprB + " / " + exprA + ")"});
                }   
                
                for (auto& [val, expr] : operations) 
                {
                    nextNums.push_back(val);
                    nextExprs.push_back(expr);  

                    if (dfs(nextNums, nextExprs)) 
                    {
                        return true;
                    }
                    
                    nextNums.pop_back();
                    nextExprs.pop_back();
                }
            }
        }
        return false;
    }
    
public:
    void judgePoint24(vector<int>& nums) 
    {
        vector<double> numbers(nums.begin(), nums.end());
        vector<string> expressions;
        for (const int& num : nums) 
        {
            expressions.push_back(to_string(num));
        }
        
        bool result = dfs(numbers, expressions);
        if (result) 
        {
            cout << "Solution: " << solution << " = 24!" << endl;
        }
        else
        {
            cout << "No Solution" << endl;
        }

        return ;
    }
};

int main()
{
    vector<int> cards1 = {4, 1, 8, 7}, cards2 = {1, 2, 1, 2};
    Solution sol;

    sol.judgePoint24(cards1);
    sol.judgePoint24(cards2);

    return 0;
}